package code.oldCode.feishuSpecializedTraining.greedy;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 26029
 * @date 2025/3/20
 * @description
 */
public class MyGreedy6 {
    // 738. 单调递增的数字
    public int monotoneIncreasingDigits(int n) {
        // 贪心的思想在于，从低位到高位，默认想要原数字（因为是最大的），但是不满足条件要处理
        // 得到数字的数组表示
        List<Integer> list = new ArrayList<>();
        int num = n;
        while (num > 0) {
            list.add(num % 10);
            num /= 10;
        }
        // 低位->高位遍历，当前位若原数字大于低位选择的数字，则当前位选择原数字-1，否则选择原数字
        int len = list.size();
        int[] temp = new int[len];
        int last = Integer.MAX_VALUE;
        int set9num = -1;
        for (int i = 0; i < len; i++) {
            if (list.get(i) > last) {
                temp[i] = list.get(i) - 1;
                set9num = i - 1; // 记录当前位选择的数字-1的情况的位置，-1代表着低位可以都选9了
            } else { // list.get(i) <= last
                temp[i] = list.get(i);
            }
            last = temp[i];
        }
        // 把高位-1之后的低位都设置为9
        for (int i = 0; i <= set9num; i++) {
            temp[i] = 9;
        }
        // 求和
        int ans = 0;
        for (int i = len - 1; i >= 0; i--) {
            ans = ans * 10 + temp[i];
        }
        return ans;
    }

    // 968. 监控二叉树
    public int minCameraCover(TreeNode root) {
        // 树型dp ※※※
        int[] ans = treeDP(root);
        return Math.min(ans[0], ans[1]);
    }

    private int[] treeDP(TreeNode root) {
        // dp[0] 当前节点装相机 dp[1] 当前节点不装相机但被覆盖到了 dp[2] 当前节点不装相机但没覆盖到
        int[] dp = new int[3]; // dp[i]表示情况i下需要的最少相机数量
        if (root == null) {
            dp[0] = Integer.MAX_VALUE / 2;
            return dp;
        }
        int[] left = treeDP(root.left);
        int[] right = treeDP(root.right);
        // 当前节点装了相机，返回左子所有情况的最小情况+右子所有情况的最小情况+1（自己装的）
        dp[0] = Math.min(left[0], Math.min(left[1], left[2])) + Math.min(right[0], Math.min(right[1], right[2])) + 1;
        // 当前节点没装相机，被覆盖，说明左右子至少有一个是装了相机的情况0，返回最小值
        dp[1] = Math.min(left[0] + Math.min(right[0], right[1]), right[0] + Math.min(left[0], left[1]));
        // 当前节点没相机也没被覆盖，说明左右子都被覆盖了，当前节点等着父节点来覆盖他
        dp[2] = left[1] + right[1];
        return dp;
    }

    public static void main(String[] args) {
        MyGreedy6 m = new MyGreedy6();
        System.out.println(m.monotoneIncreasingDigits(332));
    }
}
